给定一个整数，求出其二进制1的个数

Counting Bits

给定一个非负整数num。对于每一个满足0 ≤ i ≤ num的数字i，计算其数字的二进制表示中1的个数，并以数组形式返回。

解法一：
先介绍一个概念： Lowbit，这是计算方法： Lowbit(a)=a&(a-1)
至于它的作用，就是把二进制a 的最后一个1干掉。
比如 Lowbit(1000100)=1000000

int* countBits(int num, int* returnSize) {
    
    *returnSize = num+1;
    int cnt;
    int i, m;
    
    int *ret = (int*)malloc(sizeof(int) * (num+1));
    
    ret[0] = 0;
    
    for(m = 1; m<= num; m++){
        cnt = 0;
        i = m;
        while(i){    //求数m中二进制1的个数
            cnt++;
            i &= (i-1);
        }
        ret[m] = cnt;
    }
    return ret;
}

解法二:
根据上面介绍的lowbit的概念，可以得到以下递推关系式
ret[n] = ret[n&(n-1)] +1;

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num +1, 0);
        ret[0] = 0;        
        for(int i = 1; i<= num; i++)
            ret[i] = ret[i&(i-1)] + 1; 
        return ret;
    }
}

解法三:
递推关系式为:

ret[n] = ret[n>>1] +m //m=n&1

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num +1, 0);
        
        ret[0] = 0;        
        
        for(int i = 1; i<= num; i++){
            int m = i&1;
            ret[i] = ret[i>>1] + m; 
        }
        return ret;
    }
};